package Algorithm.Tree;

/**
 * @Author cj
 * @Date 2022/9/13 21:47
 */
public class getMaxDistance {

    static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int val) {
            this.value = val;
        }
    }

    class ReturnType {
        public int maxDistance;
        public int height;

        public ReturnType(int maxDistance, int height) {
            this.maxDistance = maxDistance;
            this.height = height;
        }
    }

    public int getMaxDistance1(Node head) {
        return process(head).maxDistance;
    }

    private ReturnType process(Node head) {
        if (head == null) {
            return new ReturnType(0, 0);
        }
        ReturnType leftData = process(head.left);
        ReturnType rightData = process(head.right);
        int height = Math.max(leftData.height, rightData.height) + 1;
        int maxDistance = Math.max(Math.max(leftData.maxDistance, rightData.maxDistance),
                leftData.height + rightData.height + 1);
        return new ReturnType(maxDistance, height);
    }
}
